Міністерство науки і освіти України.
Національний університет “Львівська політехніка”
Інститут комп’ютерних наук та інформаційних технологій.
Кафедра ПЗ
Звіт
До лабораторної роботи №4
За курсом «Алгоритми і структури даних».
Тема роботи: Ознайомлення із методами сортування. Алгоритм Шела.
Мета роботи: Вивчити та дослідити методи сортування, як один із методів обробки даних. Ознайомитись із методом сортування Шела. Виконати лабораторну роботу використавши здобуті знання по методам сортування, зокрема по методу Шела.
ТЕОРЕТИЧНІ ВІДОМОСТІ
Сортування Шелла є досить цікавою модифікацією алгоритму сортування простими вставками.
Розглянемо наступний алгоритм сортування масиву а[0].. а[15].
1. Спочатку сортуємо простими вставками кожні 8 груп з 2-х елементів.
2. Потім сортуємо кожну з чотирьох груп по 4 елементи.
У нульовій групі будуть елементи 4, 12, 13, 18, в першій - 3, 5, 8, 9.
3. Далі сортуємо 2 групи по 8 елементів.
4. В кінці сортуємо вставками усі 16 елементів.
Очевидно, лише останнє сортування необхідне, щоб розташувати всі елементи по своїх місцях. Так навіщо потрібні останні ?
Hасправді вони просувають елементи максимально близько до відповідних позицій, так що в останній стадії число переміщень буде дуже маленьке. Послідовність і так майже відсортована.
Єдиною характеристикою сортування Шелла є приріст - відстань між сортованими елементами, залежно від проходу. В кінці приріст завжди рівний одиниці – мет3од завершується звичайним сортуванням вставками, але саме послідовність приростів визначає зростання ефективності.
Використаний в прикладі набір: 8, 4, 2, 1 - непоганий вибір, особливо, коли кількість елементів - ступінь двійки. Проте набагато кращий варіант запропонував Р.Седжвік. Його послідовність має вигляд
При використанні таких приростів середня кількість операцій: O(n7/6), у гіршому разі - порядку O(n4/3).
Завдання:
Впорядкувати одновимірний масив методом Шела. Повторити декілька раз з різною кількістю елементів та порівняти час виконання.
Код програми
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<conio.h>
void Shell_sort( int a[], int n )
{
int z,step,i,j,tmp;
for( step = n/2 ; step>0 ; step >>= 1){
for( i=0; i<(n-step); ++i ){
j = i;
while ( (j>=0) && (a[j]>a[j+step]) )
{
tmp = a[j];
a[j] = a[j+step];
a[j+step] = tmp;
--j;
}}}}
int verify(int N[], int d)
{
int k;
for (k=0;k<d-1;k++)
if (N[k]>N[k+1])
return 0;
return 1;
}
void main(void)
{
int N[100000],M[100000];
int i,j,m;
int C[5]={10000,20000,50000,80000,100000};
clock_t start, end;
clrscr();
for (i=0;i<5;i++)
{
for (j=0;j<C[i];j++)
N[j]=rand();
start=clock();
Shell_sort (N, C[i]);
end=clock();
break;
printf ("%d - %.3f - %s\n", C[i], (end-start)/CLK_TCK, verify(N, C[i]) ? "OK" : "Error");
}
getch();
}
Протокол роботи програми:
Висновок: середня кількість операцій, яку викнує алгоритм O(n7/6), у гіршому разі - порядку O(n4/3).
